package com.atguigui.leetcode;

/**
 * 808.分汤
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/11/21 16:46
 */
public class P808SoupServings {

    public static void main(String[] args) {
        Solution solution = new P808SoupServings().new Solution();
        // TO TEST
    }

    class Solution {
        public double soupServings(int n) {
            //我们考虑多大的 nnn 能够配合精度误差 10^-5
            //  来减少计算量：一个可行的操作是利用上述的 DP 思路 + 二分的方式找到符合精度要求的验算值（不超过 200200200）
            n = Math.min(200, (int) Math.ceil(n / 25.0));
            double[][] f = new double[n + 10][n + 10];
            //初始化边界
            f[0][0] = 0.5;
            for (int j = 1; j <= n; j++) {
                f[0][j] = 1;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    double a = f[Math.max(i - 4, 0)][j];
                    double b = f[Math.max(i - 3, 0)][Math.max(j - 1, 0)];
                    double c = f[Math.max(i - 2, 0)][Math.max(j - 2, 0)];
                    double d = f[Math.max(i - 1, 0)][Math.max(j - 3, 0)];
                    f[i][j] = 0.25 * (a + b + c + d);
                }
            }

            return f[n][n];
        }
    }
}
